package cn.xiaolang.function.data_structure;

import lombok.Data;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 栈最小值
 * <p>
 * 请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
 * <p>
 * 示例：
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.getMin();   --> 返回 -3.
 * minStack.pop();
 * minStack.top();      --> 返回 0.
 * minStack.getMin();   --> 返回 -2.
 */
public class No13minStack {

    public static void main(String[] args) {
        MinStack2 minStack = new MinStack2();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        // --> 返回 -3.
        System.out.println(minStack.getMin());
        minStack.pop();
        // --> 返回 0.
        System.out.println(minStack.top());
        // --> 返回 -2.
        System.out.println(minStack.getMin());

    }

    @Data
    static class StackNode {
        // 节点对应的最小值
        private Integer minVal;
        private Integer curVal;
        private StackNode next;

        public StackNode(Integer minVal, Integer curVal, StackNode next) {
            this.minVal = minVal;
            this.curVal = curVal;
            this.next = next;
        }
    }

    /**
     * 1.StackNode自定义节点内容
     * 2.每次push操作时，计算当前节点的最小值
     * 3.每次pop操作时，指向节点的下一个节点即可
     */
    static class MinStack2 {

        //链表头，相当于栈顶
        private StackNode head;

        public MinStack2() {
        }

        public void push(int x) {
            if (head == null) {
                head = new StackNode(x, x, null);
            } else {
                head = new StackNode(Math.min(x, head.minVal), x, head);
            }
        }

        public void pop() {
            if (head != null) {
                head = head.next;
            }
        }

        public int top() {
            if (head != null) {
                return head.curVal;
            }
            return -1;
        }

        public int getMin() {
            if (head != null) {
                return head.minVal;
            }
            return -1;
        }
    }


    /**
     * 1.通过一个辅助栈minVal来存放栈中的最小值；
     * 2.每次push操作时，若新元素小于等于minVal栈顶元素，则该元素同时进两个栈，否则只进普通的stk栈；
     * 3.每次pop操作时，若stk栈顶元素等于minVal栈顶元素，则同时弹出两个栈顶元素，否则只弹出stk栈顶元素。
     */
    static class MinStack {

        /**
         * initialize your data structure here.
         */
        private final Deque<Integer> stk = new ArrayDeque<>();
        private final Deque<Integer> minVal = new ArrayDeque<>();

        public MinStack() {
        }

        public void push(int x) {
            if (minVal.isEmpty() || x <= minVal.getFirst()) {
                // 小于 minVal的第一个值，则把x作为minVal第一个值
                minVal.push(x);
            }
            stk.push(x);
        }

        public void pop() {
            Integer pop = stk.pop();
            if (pop.equals(minVal.getFirst())) {
                minVal.removeFirst();
            }
        }

        public int top() {
            return stk.getFirst();
        }

        public int getMin() {
            return minVal.getFirst();
        }
    }


}
